#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
using namespace std;



class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr)
            return ans;

        TreeNode* cur = root;
        stack<TreeNode*> st;
        TreeNode* pre = nullptr;
        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode* top = st.top();

            if (top->right == nullptr || top->right == pre)
            {
                pre = top;
                ans.push_back(top->val);
                st.pop();
            }
            else
            {
                cur = top->right;
            }
        }
        return ans;
    }
};

int main()
{

	return 0;
}
